package dataStrcture;


public class SegmentTree {

	int[] nums;
	int[] segmentTree;

	public SegmentTree(int[] nums) {
		this.nums = nums;
		if (nums == null || nums.length <= 0) {
			return;
		}
		// 内存占用大约为4倍的点数，所以建数组的时候为4 * N
		segmentTree = new int[nums.length * 4];
		build(0, 0, nums.length - 1);
		System.out.println("----");
		for (int i = 0; i < segmentTree.length; i++) {
			System.out.print(segmentTree[i] + "  ");
		}
		System.out.println();
	}

	public void build(int num, int left, int right) {
		System.out.println("num: " + num);
		if (left == right) {
			segmentTree[num] = nums[left];
			return;
		}
		int mid = (left + right) / 2;
		System.out.println("num: " + num + " middle: " + mid);
		build(num * 2 + 1, left, mid);
		build(num * 2 + 2, mid + 1, right);
		// 这个根据具体情况具体写，题目上是求和，所以这里是加
		// 如果变成最大值，那么这儿应该相应的改成最大值
		segmentTree[num] = segmentTree[num * 2 + 1] + segmentTree[num * 2 + 2];
	}

	public void update(int i, int val) {
		update(0, 0, nums.length - 1, i, val - nums[i]);
		nums[i] = val;
	}

	public void update(int num, int left, int right, int x, int y) {
		if (left == right) {
			segmentTree[num] += y;
			return;
		}
		int mid = (left + right) / 2;
		// 寻找到x所对应的tree[num]
		if (x <= mid) {
			update(num * 2 + 1, left, mid, x, y);
		} else {
			update(num * 2 + 2, mid + 1, right, x, y);
		}
		segmentTree[num] = segmentTree[num * 2 + 1] + segmentTree[num * 2 + 2];
	}

	public int sumRange(int i, int j) {
		return query(0, 0, nums.length - 1, i, j);
	}

	public int query(int num, int left, int right, int x, int y) {
		// 此时tree[num]就已经是这一部分的有效数据了，所以直接return即可
		if (x <= left && y >= right) {
			return segmentTree[num];
		}
		int mid = (left + right) / 2;
		int ans = 0;
		if (x <= mid)
			ans += query(num * 2 + 1, left, mid, x, y);
		if (y > mid)
			ans += query(num * 2 + 2, mid + 1, right, x, y);
		return ans;
	}

}
